package com.sfx.算法专题.双指针.n数之和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-07-26
 * Time: 10:28
 */
public class Code_6_fourSum {
    static class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int i =0;i<nums.length;++i) {
                if(nums[i]>0&&nums[i]>target) break;
                if(i>=1 && nums[i] == nums[i-1]) continue;
                for(int j = i+1;j<nums.length;++j) {
                    if(j-1>i && nums[j] == nums[j-1]) continue;
                    int l = j + 1;
                    int r = nums.length -1;
                    while(l < r) {
                        int sum = nums[i] + nums[j] + nums[l] + nums[r];
                        if(sum == target) {
                            res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[l],nums[r])));
                            l++;
                            r--;
                            //注意去重
                            // 4 4 5
                            while(l<r && nums[l] == nums[l-1]) l++;
                            while(l<r && nums[r] == nums[r+1]) r--;
                        } else if(sum > target) {
                            r --;
                        }else {
                            l++;
                        }
                    }
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,-2,-5,-4,-3,3,3,5};
        Solution solution = new Solution();
        solution.fourSum(nums,-11);
    }
}